We consider fundamental scheduling problems motivated by energy issues. Inthis framework, we are given a set of jobs, each with a release time, deadlineand required processing length. The jobs need to be scheduled on a machine sothat at most g jobs are active at any given time. The duration for which amachine is active (i.e., "on") is referred to as its active time. The goal isto find a feasible schedule for all jobs, minimizing the total active time.When preemption is allowed at integer time points, we show that a minimalfeasible schedule already yields a 3-approximation (and this bound is tight)and we further improve this to a 2-approximation via LP rounding techniques.Our second contribution is for the non-preemptive version of this problem.However, since even asking if a feasible schedule on one machine exists isNP-hard, we allow for an unbounded number of virtual machines, each havingcapacity of g. This problem is known as the busy time problem in the literatureand a 4-approximation is known for this problem. We develop a new combinatorialalgorithm that gives a 3-approximation. Furthermore, we consider the preemptivebusy time problem, giving a simple and exact greedy algorithm when unboundedparallelism is allowed, i.e., g is unbounded. For arbitrary g, this yields analgorithm that is 2-approximate.
展开▼
